package tree

func diameterOfBinaryTree(root *TreeNode) int {
	ans := 0
	q := []*TreeNode{}
	q = append(q, root)
	for len(q) > 0 {
		node := q[0]
		q = q[1:]
		ans = max(ans, maxDepth(node.Left)+maxDepth(node.Right))
		if node.Left != nil {
			q = append(q, node.Left)
		}
		if node.Right != nil {
			q = append(q, node.Right)
		}
	}
	return ans
}

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(maxDepth(root.Left), maxDepth(root.Right)) + 1
}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}
